using System.Collections.Generic;

namespace AlgorithmPractice;

/// <summary>
/// 从指定的几种面额中，计算某个金额有几种组合方式
/// </summary>
public class Combination
{
    /// <summary>
    /// 指定面额集合
    /// </summary>
    /// <typeparam name="int"></typeparam>
    /// <returns></returns>
    private static readonly IList<int> _denomination = new List<int>() {1, 2, 5, 10};

    /// <summary>
    /// 使用递归找出尽可能多的组合
    /// </summary>
    /// <param name="amount">金额</param>
    /// <param name="result">保存当前组合的解</param>
    public static void Get(int amount, List<int> result)
    {
        //满足条件的解，结束调用，输出解
        if (amount == 0)
        {
            System.Console.WriteLine($"组合方式：{string.Join(",", result)}");
            return;
        }
        //不满足条件，结束调用，不输出

        if (amount < 0)
            return;

        foreach (var d in _denomination)
        {
            var newResult =
                System.Text.Json.JsonSerializer.Deserialize<List<int>>(
                    System.Text.Json.JsonSerializer.Serialize(result));
            newResult.Add(d);
            Get(amount - d, newResult);
        }
    }
}